#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <memory>
#include <cctype>
#include <algorithm>

// 抽象表达式类
class Expression {
public:
    virtual ~Expression() = default;
    virtual int accept(class Visitor& visitor) = 0;
};

// 数字表达式类
class NumberExpression : public Expression {
public:
    NumberExpression(int value) : value(value) {}

    int accept(Visitor& visitor) override;

    int getValue() const { return value; }

private:
    int value;
};

// 二元运算表达式类
class BinaryExpression : public Expression {
public:
    BinaryExpression(std::shared_ptr<Expression> left,
                     char op,
                     std::shared_ptr<Expression> right)
            : left(left), op(op), right(right) {}

    int accept(Visitor& visitor) override;

    std::shared_ptr<Expression> getLeft() const { return left; }
    std::shared_ptr<Expression> getRight() const { return right; }
    char getOp() const { return op; }

private:
    std::shared_ptr<Expression> left;
    char op;
    std::shared_ptr<Expression> right;
};

// 访问者抽象类
class Visitor {
public:
    virtual ~Visitor() = default;
    virtual int visit(NumberExpression& numberExpression) = 0;
    virtual int visit(BinaryExpression& binaryExpression) = 0;
};

// 具体求值访问者类
class EvaluateVisitor : public Visitor {
public:
    int visit(NumberExpression& numberExpression) override {
        return numberExpression.getValue();
    }

    int visit(BinaryExpression& binaryExpression) override {
        int leftValue = binaryExpression.getLeft()->accept(*this);
        int rightValue = binaryExpression.getRight()->accept(*this);
        switch (binaryExpression.getOp()) {
            case '+':
                return leftValue + rightValue;
            case '-':
                return leftValue - rightValue;
            case '*':
                return leftValue * rightValue;
            case '/':
                return leftValue / rightValue;
            default:
                throw std::runtime_error("Invalid operator");
        }
    }
};

// 词法分析相关函数
std::vector<std::string> tokenize(const std::string& input) {
    std::vector<std::string> tokens;
    std::stringstream ss(input);
    std::string token;
    while (ss >> token) {
        tokens.push_back(token);
    }
    return tokens;
}

// 语法分析相关函数，构建表达式树
std::shared_ptr<Expression> parseExpression(const std::vector<std::string>& tokens, int& index);

std::shared_ptr<Expression> parseTerm(const std::vector<std::string>& tokens, int& index);

std::shared_ptr<Expression> parseFactor(const std::vector<std::string>& tokens, int& index);

std::shared_ptr<Expression> parseExpression(const std::vector<std::string>& tokens, int& index) {
    std::shared_ptr<Expression> left = parseTerm(tokens, index);
    while (index < tokens.size() && (tokens[index] == "+" || tokens[index] == "-")) {
        char op = tokens[index++].front();
        std::shared_ptr<Expression> right = parseTerm(tokens, index);
        left = std::make_shared<BinaryExpression>(left, op, right);
    }
    return left;
}

std::shared_ptr<Expression> parseTerm(const std::vector<std::string>& tokens, int& index) {
    std::shared_ptr<Expression> left = parseFactor(tokens, index);
    while (index < tokens.size() && (tokens[index] == "*" || tokens[index] == "/")) {
        char op = tokens[index++].front();
        std::shared_ptr<Expression> right = parseFactor(tokens, index);
        left = std::make_shared<BinaryExpression>(left, op, right);
    }
    return left;
}

std::shared_ptr<Expression> parseFactor(const std::vector<std::string>& tokens, int& index) {
    if (tokens[index].front() == '(') {
        index++;
        std::shared_ptr<Expression> result = parseExpression(tokens, index);
        if (tokens[index++].front()!= ')') {
            throw std::runtime_error("Missing closing parenthesis");
        }
        return result;
    } else {
        int value;
        std::stringstream(tokens[index++]) >> value;
        return std::make_shared<NumberExpression>(value);
    }
}

// 数字表达式类实现accept方法
int NumberExpression::accept(Visitor& visitor) {
    return visitor.visit(*this);
}

// 二元运算表达式类实现accept方法
int BinaryExpression::accept(Visitor& visitor) {
    return visitor.visit(*this);
}

int main() {
    std::string input;
    std::cout << "请输入四则运算表达式（例如：(1+3)*3+5-2+6/3）：";
    std::getline(std::cin, input);
    std::vector<std::string> tokens = tokenize(input);
    int index = 0;
    std::shared_ptr<Expression> expression = parseExpression(tokens, index);
    EvaluateVisitor evaluator;
    int result = expression->accept(evaluator);
    std::cout << "计算结果为：" << result << std::endl;
    return 0;
}
